/**
 * @author smallwang
 * @email justdoalitter@gmail.com
 * @create date 2025-01-31 17:03:02
 * @modify date 2025-01-31 17:03:02
 * @desc [description]
 */
package ltd.smallwang;

import ltd.smallwang.common.ListNode;

public class Leetcode0086 {
  public ListNode partition(ListNode head, int x) {
    ListNode dumpLeft = new ListNode(0);
    ListNode dumpLeftHead = dumpLeft;
    ListNode dumpRight = new ListNode(0);
    ListNode dumpRightHead = dumpRight;
    while (head != null) {
      if (head.val < x) {
        dumpLeft.next = head;
        dumpLeft = dumpLeft.next;
      } else {
        dumpRight.next = head;
        dumpRight = dumpRight.next;
      }
      head = head.next;
    }
    if (dumpLeftHead.next == null) {
      dumpRight.next = null;
      return dumpRightHead.next;
    }
    dumpLeft.next = dumpRightHead.next;
    dumpRight.next = null;
    return dumpLeftHead.next;
  }
}
